1. Field of the Invention
The present invention relates to an image coding device, and more particularly to a reversible coding method for coding an input image of multi-level.
2. Discussion of the Related Art
The arithmetic coding method, which is a kind of the entropy coding method, is a high-efficiency coding method in which as input data increases, the coding efficiency asymptotically approaches to the entropy. An example actually using the arithmetic coding method is JBIG (Joint Bi-level Image Experts Group) as the international standard of the bi-level reversible coding method. In the JBIG, the coding efficiency is improved by additionally incorporating the state sorting technique using adjoining pixels into the arithmetic coding method.
According to the conventional rules, the combination of pixel value or values of adjoining pixel or pixels is referred to as "context". The combination of the context and the pixel values of marked pixels is referred to as "circumjacent state".
Generally, the term "arithmetic coding method" indicates a coding method handling binary or bi-level data. With recent progressive advancement of the image processing technique, there is an increasing demand of developing the coding methods for the multi-level image processing. In this circumstance, designers are constantly under pressure of developing the applications of the arithmetic coding method to the multi-level image processing.
Before the multi-level image is compressed by an ordinary arithmetic coding method, the multi-level image must be converted into two-level data (see "INTERNATIONAL STANDARD FOR MULTI-MEDIA CODING", p. 80, written by Hiroshi Yasuda, published by Maruzen Co., Ltd.). A bit plane method, for example, may be used for this pre-processing for the binarizing process of the multi-level data. In the bit plane method, the multi-level image is converted into two-level data by slicing the multi-level image every data.
Meanwhile, it is known that in compressing the multi-level image data, the coding method which handles the image data as multi-level image provides a higher coding efficiency than the method which slices the image data into bit planes (see the above article, "INTERNATIONAL STANDARD FOR MULTI-MEDIA CODING", p. 80).
A coding method constructed by extending the arithmetic coding method so as to handle the multi-level image as intact is proposed (see the above article, "INTERNATIONAL STANDARD FOR MULTI-MEDIA CODING", p. 81). In the bi-level arithmetic coding method, codes are produced by dividing the number line into two equal segments. The extension of the arithmetic coding method may readily be realized by dividing the number line into equal segments of more than two.
However, when the arithmetic coding method is applied for the coding of the multi-level image, some problems arise. These problems will be described. The first problem follows.
1) High computing accuracy is required. PA1 2) A large-capacity memory is required corresponding to the number of circumjacent states. PA1 3) It is difficult to estimate a probability of occurrence of each circumjacent state.
This arises from the increase of the number of divisions of the number line. A computing accuracy attained by an ordinary computer suffices for the computing accuracy required for the arithmetic coding method. However, this is problematic where a high processing speed is required at the sacrifice of the computing accuracy. This problem will be solved with the advanced hardware technology. Hence, no further discussion thereof will be given here.
Second and third problems arise from the fact that in the multi-level arithmetic coding method, the number of circumjacent states is considerably increased when comparing with the bi-level arithmetic coding method. The approach using the adjoining pixels is indeed an effective means to improve the coding efficiency. However, when the number of adjoining pixels is increased, the number of circumjacent states is greatly increased. In JBIG, ten adjoining pixels are used, and these are quartered. Circumjacent states of 2.sup.2 =4,096 are used. If the same is correspondingly applied to the 8-bit image, the number of circumjacent states is approximately 8.times.10.sup.28. The number of circumjacent states for the bi-level arithmetic coding method and that for the multi-level arithmetic coding method are comparatively tabulated in Table 1. In the table, "dpi" is the abbreviation of dot per inch.
TABLE 1 __________________________________________________________________________ Multi- Bi-level level No. of arithmetic arithmetic pixels of Coding method coding coding A4 __________________________________________________________________________ No. of 0 10 JBIG 0 2 200 400 adjoining dpi dpi pixels No. of 2 2048 8192 256 *17 .times. 10.sup.6 *3.5 .times. 10.sup.6 *14 .times. 10.sup.6 circumjacent states (No. of pixels) __________________________________________________________________________ *: Approximately
The following two problems may be enumerated for the specific problems arising from the increase of the circumjacent states.
For the problem 2), since the number line is divided in accordance with an occurrence probability of each state, a memory for storing the occurrence probabilities of the circumjacent states is required. The problem 3) arises from the fact that the number of circumjacent states is considerably large when comparing with the image data as input data.
In the study on the multi-level arithmetic coding method, the approach to reduce the total number of circumjacent states by omitting the circumjacent states having less influence has been employed by most of research workers. The operation to reduce the total number of circumjacent states by omitting the circumjacent states having less influence is referred to as "degeneration". If the degeneration of the number of circumjacent states is realized, both the problems 2) and 3) could be solved because these problems arise from the excessive number of circumjacent states. For the study based on this inference, reference is made to "A State Degeneration Method for Source Encoding of Multi-Level Images" by Kato and Yasuda, The Institute of Electronics, Information and Communication Engineers, Technical Report, IE80-108.
The degeneration of circumjacent states goes against the approach to improve the coding efficiency by increasing the number of circumjacent states. It would be estimated that the degeneration has the following problems.
Degradation of the coding efficiency would be unavoidable in principle although a degree of the coding efficiency reduction depends on the degeneration method used.
In the approach in which parameters for the degeneration are determined depending on the image, as in the above article, "A State Degeneration Method for Source Encoding of Multi-Level Images", a load to the degeneration process is large.
The dependency of the coding efficiency on the image may be problematic in the degeneration system of the fixed type, described by Imanaka et al., in their paper "High-Efficiency Coding Method of High-Tone Image", The '82 Institute of Electronics and Communication Engineers, Communication Section, National Convention S3-8.
Therefore, it is ideal to realize the multi-level arithmetic coding method without degeneration. It is expected that the problem 2) will be solved with advancement of hardware technology, as of the problem 1). The basic problem hindering the realization of the multi-level arithmetic coding method resides in the problem 3) of the probability estimation. Let us consider the problem 3) of the probability estimation.
The formula of estimating the occurrence probability will first be described. The conventional technique estimates the occurrence probability of each circumjacent state by using the number of occurrences of the circumjacent state in the processed data. In the simplest example, an occurrence probability of the circumjacent state can be estimated by the following expression. ##EQU1## In the above expression, n(a) represents the number of occurrences of the circumjacent state up to the present time. In the denominator on the right side, all the existing circumjacent states are summed.
Some other probability estimating methods than the above one exist. In the document of the JBIG, a formula called the estimation of Bayes is described (ISO/IEC 11544, Annex D). ##EQU2## where .delta. represents a constant between 0 and 1. What is actually used in JBIG is a probability transition obtained referring to a predetermined transition table.
The reason why degradation of an accuracy of the estimation of the occurrence probability leads to the low coding efficiency in the arithmetic coding method, will be described.
[Average code length and probability estimation in the arithmetic coding method]
When the occurrence probabilities for symbols a, b, . . . 2x are estimated by dividing the numbers of occurrences n(a), n(b), . . . , n(x) by a data length n, viz., using the formula (1), an average code length B in the arithmetic coding method is expressed by the following expression. EQU B=[n(a)log.sub.2 (n(a)/n)+n(b)log.sub.2 (n(b)/n)++n(x)log.sub.2 (n(x)/n]/n(3)
where [ ] indicates the operation of raising fractions to unit. A theoretical value B.sub.th representative of the lower limit of the average code length B may be expressed by the entropy according to Shannon's formula. EQU B.sub.th =p(a)log.sub.2 p(a)+p(b)log.sub.2 p(b)++p(x)log.sub.2 p(x)(4)
where p(a) represents a theoretical value of the occurrence probability of a circumjacent state a.
From the above description, it is seen that as the probability estimation contained in the right side of the expression (3) is more exact, the coding efficiency asymptotically approaches to a value given by the expression (4), viz., the theoretical value. Conversely, if the accuracy of the probability estimation is degraded, the average code length B increases. Where the input data is stationary, viz., the probability distribution little varies, the probability estimation by the expression (3) can be done relatively exactly.
A coding device based on the conventional arithmetic coding method by using the estimation method of the expression (1) or (2) will be described. In FIGS. 15 (a) and 15 (b) showing the arrangement of a conventional arithmetic coding/decoding system, FIG. 15 (a) shows a coding device and FIG. 15 (b) shows a decoding device. The illustrated arithmetic coding/decoding system is the arithmetic coding/decoding system, somewhat modified, that is disclosed in "IBM Journal of Research and Development" Vol. 32-No. 6(1988), p.754-FIG. 1. In the figure, reference numeral 10 designates an image input portion; 20, an image analyzing portion; 30, a probability estimating portion; 40, a code word generating portion; 50, a code output portion; 70, a code input portion; 80, a code word analyzing portion; 90, an image output portion; 110, image data; 120, pixel value data; 130, circumjacent state data; 140, probability estimation data; 150, code word data; 210, code data; and 220, pixel value data.
The details of the arithmetic coding/decoding system shown in FIGS. 15 (a) and 15 (b) will be described. The coding device of FIG. 15 (a) is arranged in the following. The image input portion 10 receives incoming input image data, and outputs it as image data 110 to the image analyzing portion 20. The image analyzing portion 20 receives the image data 110, and transfers a pixel value of a pixel to be coded or a marked pixel as pixel value data 120 to the code word generating portion 40. The same also transfers a pixel value of an adjoining pixel as circumjacent state data 130 to the probability estimating portion 30. The probability estimating portion 30 receives the circumjacent state data 130, and transfers probability estimation data 140, which corresponds to the circumjacent state data 130, to the code word generating portion 40, and then updates the probability estimation data retained therein. The code word generating portion 40 generates a code word by using the probability estimation data 140 and the pixel value data 120, and transfers the generated code word as code word data 150 to the code output portion 50. The code output portion 50 outputs the code word data 150 as output code signal.
Next, the details of the decoding device shown in FIG. 15 (b) will be described. In the description, like or equivalent portions will be designated by like reference numerals in FIG. 15 (a) showing the coding device, with omission of description of the details thereof. The code input portion 70 receives an incoming input code signal, and transfers it as code data 210 to the code word analyzing portion 80. The code word analyzing portion 80 decodes the code data 210 by using probability estimation data 140 coming from the probability estimating portion. Then, it transfers the pixel value data 220 as the decoding result to the image output portion 90. The image output portion 90 outputs the pixel value data 220 as output data, while at the same time transfers image data 110 to the image analyzing portion 20.
The operations of the arithmetic coding/decoding system thus constructed will be described. FIGS. 2 (a) and 2 (b) are flowcharts showing the operations of the coding device of FIG. 15 (a) and the decoding device of FIG. 15 (b), respectively. In the figures, the portions enclosed by dotted lines are common to the coding procedure and the decoding procedure. FIG. 16 shows a flowchart showing step S60.
The coding process will first be described with reference to FIG. 2 (a). In step S10, the image input portion 10 performs an image input process. The input result is converted into image data 110, and transferred to the image analyzing portion 20. In step S20, the image analyzing portion 20 combines the pixel value or values of a predetermined adjoining pixel or pixels to determine a context. In step S30, a pixel value of a marked pixel is added to the context determined in step S20, thereby forming circumjacent state data 130, and the result or the circumjacent state data 130 is transferred to the probability estimating portion 30. The probability estimating portion 30 transfers the probability estimation data 140 to the code word generating portion 40 on the basis of the data of the context contained in the circumjacent state data 130. In step S40, the code word generating portion 40 generates code word data 150 using the circumjacent state data 130 and the pixel value data 120, by the arithmetic coding method. In step S50, the code output portion 50 outputs code data to exterior.
The process in step S60 will be described with reference to FIG. 16. In step S210, the probability estimation data (stored in the probability estimating portion 30) corresponding to the circumjacent state data 130 is updated by using the expression (1), for example. If required, another probability estimation data is also updated. For example, where the probability estimation data per se is retained in the probability estimating portion 30, when the estimation by the expression (1) is used, another circumjacent state of the same context must be updated.
In step S70, if all the input image data 110 have been coded, the process ends. If not yet coded, the process flow returns to step S10.
The decoding process will be described with reference to FIG. 2 (b). The same portions as those in the coding process will not be described. In step S110, the code input portion 70 executes a code input process. The input result is converted into code data 210, and the code data is transferred to the code word analyzing portion 80. Step S20 is the same as the corresponding one in the coding process except that the image data 110 for determining the context is received from the image output portion 90. In step S140, the code word analyzing portion 80 generates pixel value data 220 using the probability estimation data 140 and the code data 210, by an arithmetic decoding method. In step S150, the image output portion 90 outputs pixel value data 220 to exterior, while at the same time transfers it as image data 110 to the image analyzing portion 20. In step S170, if all the code data 210 have been coded, the process ends. If not yet coded, the process flow returns to step S110.
In the above operation, the determining of the context in step S20 is carried out using a predetermined adjoining pixel.
The conventional arithmetic coding/decoding system thus arranged cannot keep the required accuracy of the probability estimation when the number of circumjacent states is increased. The reason for this will be described hereinafter. In the multi-level arithmetic coding system, the number of input data is extremely small when comparing with the number of circumjacent states, as already described. From the withstand of the probability estimation, the cause of this can be described such that the processing of the input data ends a probability distribution is settled down in a stationary state. In usual language, it can be described such that the data processing per se ends before the processed data is statistically processed to such an extent as to estimate an occurrence probability of unprocessed data groups from the result of the statistically processed data.
From the above description, it is seen that in a case where an excessive number of circumjacent states exists, viz., a stationary state is not set up in the input data, it is impossible to obtain a good probability estimation when the conventional arithmetic coding method is used. As a consequence, it is safe to say that the solution to this problem is to speed up the processing of the probability estimation.
Thus, the problem on the probability estimation, particularly the speed-up of the processing, is the most serious obstacle in realizing the multi-level arithmetic coding system.